package first_practice;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-114-二叉树展开为链表
 * @date 2025/4/15 10:34
 */
public class Solution114 {
//    public void flatten(TreeNode root) {
//        List<TreeNode> nodes = new ArrayList<>();
//        preorder(root, nodes);
//        for (int i = 1; i < nodes.size(); i++) {
//            root.left = null;
//            root.right = nodes.get(i);
//            root = root.right;
//        }
//    }
//
//    private void preorder(TreeNode root, List<TreeNode> nodes) {
//        if (root == null)
//            return;
//        nodes.add(root);
//        preorder(root.left, nodes);
//        preorder(root.right, nodes);
//    }

    /*public void flatten(TreeNode root) {
        // 一次遍历即可,利用stack维护节点信息,边遍历边维护
        if (root == null)
            return;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            // 开始构造链表
            if (prev != null) {
                prev.left = null;
                prev.right = curr;
            }

            if (curr.right != null) {
                stack.push(curr.right);
            }
            if (curr.left != null) {
                stack.push(curr.left);
            }
            prev = curr;
        }
    }*/

    /**
     * O(1)空间复杂度
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.right = next;
                curr.left = null;
            }
            curr = curr.right;
        }
    }
}
